package 找树左下角的值;

public class Solution2 {
    private int maxDepth = Integer.MIN_VALUE;
    private int result;

    public int findBottomLeftValue(TreeNode root) {
        // 递归 + 回溯
        // 1.递归参数：父节点和当前节点的depth。不需要返回值
        // 2.递归的终止条件：当遇到叶子节点时
        // 3.先遍历左子树，然后遍历右子树。只要遍历到叶子节点的时，就需要更新当前节点的深度，并且和最大深度进行比较
        // 如果 depth > maxDepth 就需要更新最大深度，并且当前节点就是当前maxDepth的最左节点(所以要更新result的值)
        traversal(root, 1);
        return result;
    }

    public void traversal(TreeNode root, int depth) {
        // 遇到叶子节点
        if (root.left == null && root.right == null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root.val;
            }
            return;
        }
        // 左
        if (root.left != null) {
            depth++;
            traversal(root.left, depth);
            depth--; // 回溯
        }
        // 右
        if (root.right != null) {
            depth++;
            traversal(root.right, depth);
            depth--; // 回溯
        }
    }
}
